CAD/CAM systems require means to store and manipulate computer representations of two- and three-dimensional objects. Moreover, there is a need to display these objects rapidly, compute their mass properties (such as volume and moments of inertia), compute if two objects interfere and so forth. One popular method for representing two- and three-dimensional objects is by means of constructive solid geometry (CSG).
To represent a solid, one uses regular set operations, union, intersection and difference, on a set of primitive solids oriented in space. The primitive solids are simple objects like blocks, balls, cones, cylinders and tori. The set operations are union, intersection and difference. Internally, an object is represented as a binary tree. The leaves of the tree are the primitive objects and the internal nodes are the set operations. FIG. 1A illustrates a three-dimensional object (bracket with a hole) and a CSG representation of that object. A more complete description of CSG solid representation can be found in A. A. G. Requicha & H. B. Voelcker, IEEE Computer Graphics and Applications, Vol. 2, No. 2, March 1982, 9-24; R. B. Tiolve & A. A. G. Requicha, Computer Aided Design, Vol. 12, No. 5, September 1980, 219-220.
One technique for generating shaded displays of three-dimensional objects or computing the volume of three-dimensional objects is to use ray casting, see S. D. Roth, Computer Graphics and Image Proc., 18, (1982) 109-144. In ray casting one computes the intersection of a family of straight lines with the three-dimensional object. Using the endpoints of the intersecting intervals, one can compute the boundary of the object. Integrating along the intervals one can compute the volume and moments of inertia of the object. Any means for computing the intersection of a large family of lines with an object represented by a CSG representation is computationally very intensive therefore time consuming.